
位运算就是把整数转换为二进制后，每位进行相应的运算得到结果。

常用的运算符共 6 种，分别为与（\texttt{\&}）、或（\texttt{|}）、异或（\texttt{\textasciicircum{}}）、取反（\texttt{\textasciitilde{}}）、左移（\texttt{<<}） 和右移（\texttt{>>}）。

\subsection{与、或、异或}

与（\texttt{\&}）或（\texttt{|}）和异或（\texttt{\textasciicircum{}}）这三者都是两者间的运算，因此在这里一起讲解。

表示把两个整数分别转换为二进制后各位逐一比较。

\begin{tabular}{cc}
\hline
运算符& 解释\\\&& 只有在两个（对应位数中）都为 1 时才为 1\\<code>& 只要在两个（对应位数中）有一个 1 时就为 1\\\textasciicircum{}& 只有两个（对应位数）不同时才为 1\\\hline
\end{tabular}

\texttt{\textasciicircum{}} 运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即 \texttt{(a \textasciicircum{} b) \textasciicircum{} b = a}。

\begin{QUOTE}{}{}
举例：

$$
\begin{aligned}
&5&=&&(101)_2\\
&6&=&&(110)_2\\
&5\tt\,\&\,6\rm&=&&(100)_2&=\ 4\\
&5\tt\,|\,\rm6&=&&(111)_2&=\ 7\\
&5\tt\,\mbox{\textasciicircum},\rm6&=&&(011)_2&=\ 3\\
\end{aligned}
$$
\end{QUOTE}

\subsection{取反}

取反是对 1 个数 $num$ 进行的计算。

\texttt{\textasciitilde{}} 把 $num$ 的补码中的 0 和 1 全部取反 （0 变为 1，1 变为 0）。

补码——正数的补码为其（二进制）本身，负数的补码是其（二进制）取反后 $+1$。

\begin{QUOTE}{}{}
举例：

$$
\begin{aligned}
5=(0000\ 0101)_2\\
5\ \text{的补码} =(1111\ 1010)_2\\
\tt\ \text{~}\rm5=(1111\ 1010)_2
\end{aligned}
$$
\end{QUOTE}

\subsection{左移和右移}

与前面的 4 种运算相似，这两种运算仍是把整数转换为二进制后进行操作。

左移（\texttt{<<}） 将转化为二进制后的数字整体向左移动。

\begin{QUOTE}{}{}
\texttt{num << i}  // 表示将 $num$ 转换为二进制后向左移动 $i$ 位（所得的值）
\end{QUOTE}

右移（\texttt{>>}） 将转化为二进制后的数字整体向右移动。

\begin{QUOTE}{}{}
\texttt{num >> i}  // 表示将 $num$ 转换为二进制后向左移动 $i$ 位（所得的值）



举例：



$$
\begin{array} { l l } { 5 } & { = ( 00000101 ) _ { 2 } } \\ { 5 < < 1 } & { = ( 00001010 ) _ { 2 } } \\ { 5 > > 1 } & { = ( 00000010 ) _ { 2 } } \end{array}
$$
\end{QUOTE}

在 C++ 中，右移操作中右侧多余的位将会被舍弃。而左侧较为复杂：对于无符号数，会在左侧补 0；而对于有符号数，则会用最高位的数补齐（Replicate most significant bit on left）。

注意：

\begin{enumerate}
\item 左移和右移是有返回值的，并非对 $num$ 本身进行操作。
\item 左移和右移的优先级低于四则运算符，例如 $x<<1+1$ 会被解释为 $x<<(1+1)$ ，所以必要的时候，要使用括号。
\end{enumerate}

\hr

\subsection{位运算的应用}

如果 $num$ 是正数，\texttt{num << i} 相当于 $num$ 乘以 2 的 $i$ 次方，而 \texttt{num >> i} 相当于 $num$ 除以 2 的 $i$ 次方。 (位运算比 \texttt{\%} 和 \texttt{/} 操作快得多)

(据 2018JSOI 夏令营，效率可以提高 60\%)

\begin{NOTE}{warning}{}
为什么要强调是正数呢？考虑一下 \texttt{-1 >> 3}

\end{NOTE}


\texttt{num * 10 = (num<<1) + (num<<3)}

\texttt{num \& 1} 相当于取 $num$ 二进制的最末位，可用于判断 $num$ 的奇偶性，二进制的最末位为 0 表示该数为偶数，最末位为 1 表示该数为奇数。

\begin{cppcode}
// 利用位运算的快捷的 swap 代码
void swap(int &a, int &b) {
  a = a ^ b;
  b = a ^ b;
  a = a ^ b;
}
\end{cppcode}

一个数的二进制表示可以看作是一个集合（0 表示不在集合中，1 表示在集合中）。比如集合 \texttt{\{1, 3, 4, 8\}}，可以表示成 \texttt{0b00000000000000000000000100011010}，十进制就是 $2^8+2^4+2^3+2^1=282$。

而对应的位运算也就可以看作是对集合进行的操作。

\begin{tabular}{crc}
\hline
操作& 集合表示& 位运算语句\\交集& a \textbackslash{}cap b& a \& b\\并集& a \textbackslash{}cup b& a | b\\补集& \textbackslash{}bar\{a\}& \textasciitilde{}a\\差集& a \textbackslash{}setminus b& \textasciitilde{}a\\对称差& a\textbackslash{}triangle b& a \textasciicircum{} b\\\hline
\end{tabular}

\hr

\subsection{位运算的常用方法}

\begin{itemize}
\item 乘以 2 运算。
\begin{cppcode}
int mulTwo(int n) {  // 计算 n*2
  return n << 1;
}
\end{cppcode}
\item 除以 2 运算。
\begin{cppcode}
int divTwo(int n) {  // 负奇数的运算不可用
  return n >> 1;     // 除以 2
}
\end{cppcode}
\item 乘以 2 的 $m$ 次方。
\begin{cppcode}
int mulTwoPower(int n, int m) {  // 计算 n*(2^m)
  return n << m;
}
\end{cppcode}
\item 除以 2 的 $m$ 次方。
\begin{cppcode}
int divTwoPower(int n, int m) {  // 计算 n/(2^m)
  return n >> m;
}
\end{cppcode}
\item 判断一个数的奇偶性。
\begin{cppcode}
boolean isOddNumber(int n) { return n & 1; }
\end{cppcode}
\item 取绝对值（某些机器上，效率比 \texttt{n > 0 ? n : -n} 高）。
\begin{cppcode}
int abs(int n) {
  return (n ^ (n >> 31)) - (n >> 31);
  /* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 - 1
     若 n 为正数 n^0=0, 数不变，若 n 为负数有 n^-1
     需要计算 n 和 - 1 的补码，然后进行异或运算，
     结果 n 变号并且为 n 的绝对值减 1，再减去 - 1 就是绝对值 */
}
\end{cppcode}
\item 取两个数的最大值（某些机器上，效率比 \texttt{a > b ? a : b} 高）。
\begin{cppcode}
int max(int a, int b) {
  return b & ((a - b) >> 31) | a & (~(a - b) >> 31);
  /* 如果 a>=b,(a-b)>>31 为 0，否则为 - 1 */
}
\end{cppcode}
\item 取两个数的最小值（某些机器上，效率比 \texttt{a > b ? b : a} 高）。
\begin{cppcode}
int min(int a, int b) {
  return a & ((a - b) >> 31) | b & (~(a - b) >> 31);
  /* 如果 a>=b,(a-b)>>31 为 0，否则为 - 1 */
}
\end{cppcode}
\item 判断符号是否相同。
\begin{cppcode}
boolean isSameSign(int x, int y) {  // 有 0 的情况例外
  return (x ^ y) >=
         0;  // true 表示 x 和 y 有相同的符号，false 表示 x,y 有相反的符号。
}
\end{cppcode}
\item 计算 2 的 $n$ 次方。
\begin{cppcode}
int getFactorialofTwo(int n) {  // n > 0
  return 1 << n;                // 2 的 n 次方
}
\end{cppcode}
\item 判断一个数是不是 2 的幂。
\begin{cppcode}
boolean isFactorialofTwo(int n) {
  return n > 0 ? (n & (n - 1)) == 0 : false;
  /* 如果是 2 的幂，n 一定是 100... n-1 就是 1111....
     所以做与运算结果为 0 */
}
\end{cppcode}
\item 对 2 的 $n$ 次方取余。
\begin{cppcode}
int quyu(int m, int n) {  // n 为 2 的次方
  return m & (n - 1);
  /* 如果是 2 的幂，n 一定是 100... n-1 就是 1111....
     所以做与运算结果保留 m 在 n 范围的非 0 的位 */
}
\end{cppcode}
\item 求两个整数的平均值。
\begin{cppcode}
int getAverage(int x, int y) {
  return (x + y) >> 1;
  ｝
\end{cppcode}
\item 遍历一个集合的子集
\begin{cppcode}
int b = 0;
do {
  // process subset b
} while (b = (b - x) & x);
\end{cppcode}
\end{itemize}

\subsection{题目推荐}

\href{http://codevs.cn/problem/2743/}{CODEVS 2743 黑白棋游戏}

\subsection{参考}

位运算技巧：\url{https://graphics.stanford.edu/~seander/bithacks.html}
